/*
All rights reserved, Biometric Computing Center, HITsz
*/

//#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

#define g_iFilterSize 35
#define g_iHalfFilterSize 17
#define g_iOrientation 6
#define PalmThRatio 0.45
#define PlaneNum 3
#define FeatureSize 512
#define DwByteMask 0x000000FF
#define SampleSize 3
#define FALSE 0
#define TRUE 1
#define WHITE 255
#define BLACK 0
#define PI 3.141592653589793
#define pi2 6.283185307179586
#define NO_OF_TEMPLATES 3
#define BOUNDARYPOINTS 500
#define HighThreshold2D 0.30
#define MidThreshold2D 0.36
#define LowThreshold2D 0.39
#define SUBIMAGEWIDTH 128
#define SUBIMAGEHEIGHT 128
#define IMAGEWIDTH 320
#define IMAGEHEIGHT 240
#define HighThreshold3D 0.50
#define MidThreshold3D 0.60
#define LowThreshold3D 0.65
#ifdef _WIN32
typedef unsigned __int64 UINT64;
#else
typedef unsigned long long UINT64;
#endif
typedef unsigned int Bit32;

typedef struct
{
	Bit32 BitPlane_0[32];
	Bit32 BitPlane_1[32];
	Bit32 BitPlane_2[32];
	Bit32 BitPlane_M[32];
} printFeature;

int g_SearchStart = 30;
int pairList[1000][2];
int pairListNum;
int maxP1Index;
int maxP2Index;
int startP1, endP1;
int startP2, endP2;
int lastP1Index;
int lastP2Index;
int holeList[2][BOUNDARYPOINTS][2];
int HoleNumber[2] = {0, 0};
int ImageWidth = IMAGEWIDTH;
int ImageHeight = IMAGEHEIGHT;
int Hole_Length = 5;
static int Hole_Width = 3;
double g_PalmThRatio = PalmThRatio;
static int g_pfFilter[g_iOrientation][g_iFilterSize * g_iFilterSize] = {0};
float g_fSigma = 4.6;
float g_f2Delta = 2.6;
int g_iCropImageWidth = 128;
int g_iCropImageHeight = 128;
const int g_iFeatureSize = 512;
int g_iShiftSize = 3;
int g_piShiftStart[31] = {0, 0, 0, 0, 1, 2, 3};
int g_piShiftEnd[31] = {29, 30, 31, 32, 32, 32, 32};
int g_BitCounterArray[256] = {
	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};

int g_iSampleSize = 3;
int bHasInit = FALSE;
int PreThreshold = 25;
int SubWidth = 128;
int SubHeight = 128;
float ROIDistFromKey = 32;
int BeginCoordinateValue = 15;
const int scan_direction = 1; //we should consider scan direction becasuse of line scan algorithm
int edge[7];
int HoleDetection(int holeList[2][BOUNDARYPOINTS][2], int HoleNumber[2], int FingerHoleStart[2][2], int FingerHoleEnd[2][2], int index, unsigned char *TF);
int LnkeyPointDetection(int Boundary[2][BOUNDARYPOINTS][2], int HoleNumber[2], int Sx[4], int Sy[4]);
void Standard(int Sx[4], int Sy[4], int OutputWidth, int OutputHeight, unsigned char *Image, unsigned char *SubImage);
int getStartPoints(unsigned char *thFlag, int edge[7]);

int HoleDetection(int holeList[2][BOUNDARYPOINTS][2], int HoleNumber[2], int FingerHoleStart[2][2], int FingerHoleEnd[2][2], int index, unsigned char *TF)
{
	int p = 0, pastp, i;
	int pastDirection = 1;
	int x, y;
	int j = 0;
	int EndDiff;
	int LM[8][2] = {{1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}};
	int contFlag = TRUE;
	holeList[index][0][0] = FingerHoleStart[index][0];
	holeList[index][0][1] = FingerHoleStart[index][1];

	while (contFlag == TRUE && p < BOUNDARYPOINTS - 1)
	{
		pastp = p;
		for (i = -2; i < 6; i++)
		{
			j = i + pastDirection;
			if (j < 0)
			{
				j = j + 8;
			}
			else if (j > 7)
			{
				j = j - 8;
			}
			x = holeList[index][p][0] + LM[j][0];
			y = holeList[index][p][1] + LM[j][1];

			if (TF[x + y * ImageWidth] == BLACK)
			{
				if (TF[(x + 1) + y * ImageWidth] == WHITE || TF[(x - 1) + y * ImageWidth] == WHITE || TF[x + (y - 1) * ImageWidth] == WHITE || TF[x + (y + 1) * ImageWidth] == WHITE)
				{
					if ((j + 4) != pastDirection && (j - 4) != pastDirection)
					{
						pastDirection = j;
						p++;
						holeList[index][p][0] = x;
						holeList[index][p][1] = y;
						break;
					}
				}
			}
		}

		if (pastp == p || p - 1 != pastp || ((holeList[index][p][0] == holeList[index][p - 1][0]) && (holeList[index][p][1] == holeList[index][p - 1][1])))
		{
			return FALSE;
		}

		if (holeList[index][p][0] == FingerHoleEnd[index][0] && p > Hole_Length) //TODO: change threshold from 10 to xxx
		{
			EndDiff = holeList[index][p][1] - FingerHoleEnd[index][1];
			if (EndDiff <= 5 && EndDiff >= -5)
			{
				if (holeList[index][p][0] != FingerHoleEnd[index][0] || holeList[index][p][1] != FingerHoleEnd[index][1])
				{
					p = p + 1;
					holeList[index][p][0] = FingerHoleEnd[index][0];
					holeList[index][p][1] = FingerHoleEnd[index][1];
				}
				contFlag = FALSE;
				break;
			}
			else
			{
				return FALSE;
			}
		}
		else if (holeList[index][p][0] > (ImageWidth * 3 / 4))
		{
			return FALSE;
		}
		if (contFlag == FALSE)
		{
			break;
		}
	}
	HoleNumber[index] = p + 1;
	if (HoleNumber[index] > BOUNDARYPOINTS - 1)
		HoleNumber[index] = BOUNDARYPOINTS - 1;

	if ((FingerHoleEnd[index][1] - FingerHoleStart[index][1]) < Hole_Width && (FingerHoleEnd[index][1] - FingerHoleStart[index][1]) > -Hole_Width)
	{
		return FALSE;
	}
	return TRUE;
}
/*
@Image: input, must be 320*240
@SubImage: output, with size 128*128
@Sx,Sy: input four points of roi rectangle,note that length of edge no need to be 128
*/
void ROIExtraction(unsigned char *Image, unsigned char *SubImage, int Sx[4], int Sy[4])
{
	int OutputWidth = 128;
	int OutputHeight = 128;
	float D;
	float R[2][2];
	float x = 0, y = 0;
	long intx = 0, inty = 0;
	int RWidth = OutputWidth - 1;
	int RHeight = OutputHeight - 1;
	float Rx, Ry;
	int bImageHeight = ImageHeight - 1;
	int bImageWidth = ImageWidth - 1;
	float a, b, c, d;
	int i, j;
	int intxy;
	int intxy1;
	int intx1y;
	int intx1y1;
	unsigned char *ImgPtr2;

	D = (float)sqrt((float)((Sx[0] - Sx[1]) * (Sx[0] - Sx[1]) + (Sy[0] - Sy[1]) * (Sy[0] - Sy[1])));
	R[0][0] = (float)(Sx[0] - Sx[3]) / D;
	R[1][1] = R[0][0];
	R[0][1] = (float)(Sy[3] - Sy[0]) / D;
	R[1][0] = -R[0][1];
	ImgPtr2 = Image;

	for (j = 0; j < OutputWidth; j++)
	{
		for (i = 0; i < OutputHeight; i++)
		{
			Rx = (float)(i * D / RHeight);
			Ry = (float)(j * D / RWidth);
			x = R[0][0] * Rx + R[0][1] * Ry + Sx[3];
			y = R[1][0] * Rx + R[1][1] * Ry + Sy[3];
			intx = (int)x;
			inty = (int)y;

			if ((-1 < intx && intx < bImageHeight) && (-1 < inty && inty < bImageWidth))
			{
				intxy = *(ImgPtr2 + (intx * ImageWidth + inty));
				intxy1 = *(ImgPtr2 + (intx * ImageWidth + inty + 1));
				intx1y = *(ImgPtr2 + ((intx + 1) * ImageWidth + inty));
				intx1y1 = *(ImgPtr2 + ((intx + 1) * ImageWidth + inty + 1));

				if (intxy > 5)
				{
					c = (float)intx1y1 - intxy1 - intx1y + intxy;
					a = intx1y - intxy - c * inty;
					b = intxy1 - intx1y + a + c * (inty - intx);
					d = intxy - a * intx - b * inty - c * intx * inty;

					SubImage[i * OutputHeight + j] = (int)(a * x + b * y + c * x * y + d);
				}
				else
				{

					SubImage[i * OutputHeight + j] = 0;
				}
			}
			else
			{

				SubImage[i * OutputHeight + j] = 0;
			}
		}
	}
}

void FillGaborFilterAngle(float fSigma, float f2Delta, float fAngle, int *pFilter)
{
	const float _2ln2 = sqrt(2 * log(2.0));
	float fK = _2ln2 * (f2Delta + 1) / (f2Delta - 1);
	float fW0 = fK / fSigma;
	float fFactor1 = -fW0 / (sqrt(2 * PI) * fK);
	float fFactor2 = -(fW0 * fW0) / (8 * fK * fK);
	float fSin = sin(fAngle);
	float fCos = cos(fAngle);
	float fTemp;
	float x, y, x1, y1;
	int fSum = 0;
	int i, j;
	float fMean;

	for (i = 0; i < g_iFilterSize; i++)
	{
		x = i - g_iHalfFilterSize;
		for (j = 0; j < g_iFilterSize; j++)
		{
			y = j - g_iHalfFilterSize;
			x1 = x * fCos + y * fSin;
			y1 = y * fCos - x * fSin;
			fTemp = 10000 * fFactor1 * exp(fFactor2 * (4 * x1 * x1 + y1 * y1));
			pFilter[i * g_iFilterSize + j] = (int)(fTemp * cos(fW0 * x * fCos + fW0 * y * fSin));
			fSum += pFilter[i * g_iFilterSize + j];
		}
	}

	fMean = (float)fSum / g_iFilterSize / g_iFilterSize;
	for (i = 0; i < g_iFilterSize; i++)
		for (j = 0; j < g_iFilterSize; j++)
			pFilter[i * g_iFilterSize + j] = (int)(pFilter[i * g_iFilterSize + j] - fMean);
}

void FillGaborFilter(float fSigma, float f2Delta)
{
	float fAngle;
	int i;
	for (i = 0; i < g_iOrientation; i++)
	{
		fAngle = PI * i / g_iOrientation;
		FillGaborFilterAngle(fSigma, f2Delta, fAngle, g_pfFilter[i]);
	}
}

void FeatureExtractionPrint(unsigned char *pbyImage, printFeature *pF2D)
{
	int iColIndex = 0, kk = 0;
	int pfSum[g_iOrientation];
	int fMax;
	int iMaxIndex;
	int i, j, x, y, iDirection;
	Bit32 dwBitMask;
	int T1, T2, T3, T4;
	int byGrayValue;
	int iMaskNum;
	int m, n;
	int iPosImageX, iPosImageY;
	Bit32 *pdwMask;
	int TempCharOff, ImageOff, FilterTempOff;
	Bit32 *pdwPlane[3];
	memset(pF2D, 0, FeatureSize);

	pdwPlane[0] = (Bit32 *)(pF2D->BitPlane_0);
	pdwPlane[1] = (Bit32 *)(pF2D->BitPlane_1);
	pdwPlane[2] = (Bit32 *)(pF2D->BitPlane_2);
	pdwMask = (Bit32 *)(pF2D->BitPlane_M);
	memset(pdwMask, 0xFF, 128);

	if (!bHasInit)
	{
		FillGaborFilter(g_fSigma, g_f2Delta);
		bHasInit = TRUE;
	}
	for (i = g_iHalfFilterSize; i < g_iCropImageHeight - g_iHalfFilterSize; i += g_iSampleSize)
	{
		dwBitMask = 0x80000000;
		for (j = g_iHalfFilterSize; j < g_iCropImageWidth - g_iHalfFilterSize; j += g_iSampleSize)
		{
			memset(pfSum, 0, sizeof(int) * g_iOrientation);

			for (x = -g_iHalfFilterSize; x <= g_iHalfFilterSize; x++)
			{
				for (y = -g_iHalfFilterSize; y <= g_iHalfFilterSize; y++)
				{
					byGrayValue = pbyImage[(i + x) * g_iCropImageWidth + j + y];
					T2 = (x + g_iHalfFilterSize) * g_iFilterSize + g_iHalfFilterSize + y;
					for (iDirection = 0; iDirection < g_iOrientation; iDirection++)
					{
						pfSum[iDirection] += byGrayValue * g_pfFilter[iDirection][T2]; //by lx
					}
				}
			}

			fMax = pfSum[0];
			iMaxIndex = 0;
			for (iDirection = 1; iDirection < 6; iDirection++)
			{
				if (pfSum[iDirection] > fMax)
				{
					fMax = pfSum[iDirection];
					iMaxIndex = iDirection;
				}
			}

			if (iMaxIndex > 0)
			{
				if (iMaxIndex < 3)
				{
					if (iMaxIndex < 2)
					{
						pdwPlane[0][iColIndex] = pdwPlane[0][iColIndex] | dwBitMask;
					}
					else
					{
						pdwPlane[0][iColIndex] = pdwPlane[0][iColIndex] | dwBitMask;
						pdwPlane[1][iColIndex] = pdwPlane[1][iColIndex] | dwBitMask;
					}
				}
				else if (iMaxIndex > 3)
				{
					if (iMaxIndex > 4)
					{
						pdwPlane[2][iColIndex] = pdwPlane[2][iColIndex] | dwBitMask;
					}
					else
					{
						pdwPlane[1][iColIndex] = pdwPlane[1][iColIndex] | dwBitMask;
						pdwPlane[2][iColIndex] = pdwPlane[2][iColIndex] | dwBitMask;
					}
				}
				else
				{
					pdwPlane[0][iColIndex] = pdwPlane[0][iColIndex] | dwBitMask;
					pdwPlane[1][iColIndex] = pdwPlane[1][iColIndex] | dwBitMask;
					pdwPlane[2][iColIndex] = pdwPlane[2][iColIndex] | dwBitMask;
				}
			}
			dwBitMask >>= 1;
		}
		iColIndex++;
	}
}

double MatchPrint(printFeature *pF2D1, printFeature *pF2D2)
{
	int i, k;
	int iDiffNum, iTotalNum;
	int iShiftX, iShiftY, iModel2Index;
	Bit32 dwPlane[PlaneNum], dwMask;
	Bit32 *pdwPlane1[PlaneNum];
	Bit32 *pdwPlane2[PlaneNum];
	Bit32 *pdwMask1;
	Bit32 *pdwMask2;
	float fMin = 3;
	float fTempMin;
	int minX, minY;
	pdwPlane1[0] = (Bit32 *)(pF2D1->BitPlane_0);
	pdwPlane1[1] = (Bit32 *)(pF2D1->BitPlane_1);
	pdwPlane1[2] = (Bit32 *)(pF2D1->BitPlane_2);
	pdwMask1 = (Bit32 *)(pF2D1->BitPlane_M);
	pdwPlane2[0] = (Bit32 *)(pF2D2->BitPlane_0);
	pdwPlane2[1] = (Bit32 *)(pF2D2->BitPlane_1);
	pdwPlane2[2] = (Bit32 *)(pF2D2->BitPlane_2);
	pdwMask2 = (Bit32 *)(pF2D2->BitPlane_M);

	for (iShiftX = -g_iShiftSize; iShiftX <= g_iShiftSize; iShiftX++)
	{
		for (iShiftY = -g_iShiftSize; iShiftY <= g_iShiftSize; iShiftY++)
		{
			iDiffNum = 0;
			iTotalNum = 0;
			for (i = g_piShiftStart[iShiftX + g_iShiftSize]; i < g_piShiftEnd[iShiftX + g_iShiftSize]; i += 2)
			{

				iModel2Index = i - iShiftX;
				if (iShiftY >= 0)
				{
					dwMask = (pdwMask1[i] & (pdwMask2[iModel2Index] >> iShiftY));
					for (k = 0; k < PlaneNum; k++)
					{

						dwPlane[k] = (pdwPlane1[k][i] ^ (pdwPlane2[k][iModel2Index] >> iShiftY));
					}
				}
				else
				{
					dwMask = (pdwMask1[i] & (pdwMask2[iModel2Index] << (-iShiftY)));
					for (k = 0; k < PlaneNum; k++)
					{

						dwPlane[k] = (pdwPlane1[k][i] ^ (pdwPlane2[k][iModel2Index] << (-iShiftY)));
					}
				}

				iTotalNum = iTotalNum + g_BitCounterArray[dwMask & DwByteMask] + g_BitCounterArray[(dwMask >> 8) & DwByteMask] + g_BitCounterArray[(dwMask >> 16) & DwByteMask] + g_BitCounterArray[(dwMask >> 24) & DwByteMask];

				for (k = 0; k < PlaneNum; k++)
				{
					iDiffNum = iDiffNum + g_BitCounterArray[dwPlane[k] & DwByteMask & dwMask] + g_BitCounterArray[(dwPlane[k] >> 8) & DwByteMask & (dwMask >> 8)] + g_BitCounterArray[(dwPlane[k] >> 16) & DwByteMask & (dwMask >> 16)] + g_BitCounterArray[(dwPlane[k] >> 24) & DwByteMask & (dwMask >> 24)];
				}
			}

			if (iTotalNum > 250)
			{
				fTempMin = (iDiffNum) / (float)(iTotalNum);
				if (fTempMin < fMin)
				{
					fMin = fTempMin;
					minX = iShiftX;
					minY = iShiftY;
				}
			}
		}
	}

	fMin /= PlaneNum;
	if (fMin > 0.43)
	{
		return fMin;
	}
	else
	{
		iShiftX = minX;
		iShiftY = minY;
		iDiffNum = 0;
		iTotalNum = 0;
		for (i = g_piShiftStart[iShiftX + g_iShiftSize]; i < g_piShiftEnd[iShiftX + g_iShiftSize]; i++)
		{
			iModel2Index = i - iShiftX;
			if (iShiftY >= 0)
			{
				dwMask = (pdwMask1[i] & (pdwMask2[iModel2Index] >> iShiftY));
				for (k = 0; k < PlaneNum; k++)
				{
					dwPlane[k] = (pdwPlane1[k][i] ^ (pdwPlane2[k][iModel2Index] >> iShiftY));
				}
			}
			else
			{
				dwMask = (pdwMask1[i] & (pdwMask2[iModel2Index] << (-iShiftY)));
				for (k = 0; k < PlaneNum; k++)
				{
					dwPlane[k] = (pdwPlane1[k][i] ^ (pdwPlane2[k][iModel2Index] << (-iShiftY)));
				}
			}

			iTotalNum = iTotalNum + g_BitCounterArray[dwMask & DwByteMask] + g_BitCounterArray[(dwMask >> 8) & DwByteMask] + g_BitCounterArray[(dwMask >> 16) & DwByteMask] + g_BitCounterArray[(dwMask >> 24) & DwByteMask];
			for (k = 0; k < PlaneNum; k++)
			{
				iDiffNum = iDiffNum + g_BitCounterArray[dwPlane[k] & DwByteMask & dwMask] + g_BitCounterArray[(dwPlane[k] >> 8) & DwByteMask & (dwMask >> 8)] + g_BitCounterArray[(dwPlane[k] >> 16) & DwByteMask & (dwMask >> 16)] + g_BitCounterArray[(dwPlane[k] >> 24) & DwByteMask & (dwMask >> 24)];
			}
		}
		fMin = (iDiffNum) / (float)(iTotalNum) / PlaneNum;
	}
	return fMin;
}

int getStartPoints(unsigned char *thFlag, int edge[7])
{
	int iSearchStart = g_SearchStart;
	int SCAN_SUCCESS = FALSE;
	int index = 0;
	int tag0, tag1;
	int findDN = 1;
	unsigned char *data = new unsigned char[ImageHeight];

	int i_start, i_end;
	if (scan_direction == 1)
	{
		/* scan postively */
		i_start = ImageHeight * 3 / 16; //8;
		i_end = ImageHeight;
	}
	else
	{
		/* scan negtively */
		i_start = 0;
		i_end = ImageHeight * 13 / 16; //ImageHeight - 8
	}

	while ((iSearchStart < ImageWidth * 3 / 4) & (SCAN_SUCCESS == FALSE))
	{
		iSearchStart += 5;
		index = 0;
		tag0 = 0;
		tag1 = 0;
		findDN = 1;

		if (scan_direction == 1)
			for (int r = 0; r < ImageHeight; r++)
				data[r] = thFlag[r * ImageWidth + iSearchStart];
		else
			for (int r = 0; r < ImageHeight; r++)
				data[r] = thFlag[(ImageHeight - 1 - r) * ImageWidth + iSearchStart];

		for (int i = i_start; i < i_end; i++)
		{
			if (findDN == 1)
			{
				if ((int)(data[i]) - (int)(data[i - 1]) < 0)
				{
					if (index == 0)
					{
						tag0++;
						edge[index] = i;
						index++;
						findDN = 0;
					}
					else if (i - edge[index - 1] > 3) //TODO:change threshold from 5 to xxx
					{
						tag0++;
						edge[index] = i;
						index++;
						findDN = 0;
					}
				}
			}
			else
			{
				if ((int)(data[i]) - (int)(data[i - 1]) > 0 && i - edge[index - 1] > 3) //TODO:change threshold from 5 to xxx
				{
					tag1++;
					edge[index] = i - 1;
					index++;
					findDN = 1;
				}
			}
			if (index >= 6)
				break;
		}

		if (tag0 >= 3 && tag1 >= 3)
		{
			edge[6] = iSearchStart;
			SCAN_SUCCESS = TRUE;
		}
	}
	delete[] data;
	return SCAN_SUCCESS;
}

int Lnpreprocessing(unsigned char *Image, unsigned char *ThresholdFlag, unsigned char *roiImg, int Sx[4], int Sy[4])
{
	int j, i, x, y, count;
	int FirsrPoint = 0;
	int LowpassValue = 0, ImageGrayValue = 0;
	int col, row;
	int Lowpass[5][5];
	int PreThresholdEnlarge = PreThreshold * 10000;
	int ChangeFlag = TRUE;
	int whilecount = 0;
	int FingerHoleStart[2][2] = {{0, 0}, {0, 0}};
	int FingerHoleEnd[2][2] = {{0, 0}, {0, 0}};
	int FingerHoleResult[2] = {FALSE, FALSE};
	int HoleFlag = FALSE;

	while (ChangeFlag == TRUE)
	{
		whilecount = whilecount + 1;
		if (whilecount >= 30)
		{
			return FALSE;
		}
		ChangeFlag = FALSE;
		for (i = BeginCoordinateValue - 2; i < ImageWidth / 4 * 3; i++)
		{
			for (j = 4; j < ImageHeight - 4; j++)
			{
				if (ThresholdFlag[i + j * ImageWidth] == BLACK)
				{
					if (ThresholdFlag[(i - 1) + j * ImageWidth] == WHITE && ThresholdFlag[(i + 1) + ImageWidth * j] == WHITE)
					{
						ThresholdFlag[i + j * ImageWidth] = WHITE;
						ChangeFlag = TRUE;
					}
					else if (ThresholdFlag[i + (j - 1) * ImageWidth] == WHITE && ThresholdFlag[i + (j + 1) * ImageWidth] == WHITE)
					{
						ThresholdFlag[i + j * ImageWidth] = WHITE;
						ChangeFlag = TRUE;
					}
				}
			}
		}
	}

	FingerHoleStart[0][0] = BeginCoordinateValue;
	FingerHoleStart[1][0] = BeginCoordinateValue;
	FingerHoleEnd[0][0] = BeginCoordinateValue;
	FingerHoleEnd[1][0] = BeginCoordinateValue;

	HoleFlag = getStartPoints(ThresholdFlag, edge);
	if (HoleFlag == FALSE)
	{
		printf("get start points error!\n");
		return FALSE;
	}

	if (scan_direction == 1)
	{
		FingerHoleStart[0][0] = edge[6];
		FingerHoleStart[0][1] = edge[0];
		FingerHoleEnd[0][0] = edge[6];
		FingerHoleEnd[0][1] = edge[1];

		FingerHoleStart[1][0] = edge[6];
		FingerHoleStart[1][1] = edge[4];
		FingerHoleEnd[1][0] = edge[6];
		FingerHoleEnd[1][1] = edge[5];
	}
	else
	{
		FingerHoleStart[1][0] = edge[6];
		FingerHoleStart[1][1] = ImageHeight - 1 - edge[1];
		FingerHoleEnd[1][0] = edge[6];
		FingerHoleEnd[1][1] = ImageHeight - 1 - edge[0];

		FingerHoleStart[0][0] = edge[6];
		FingerHoleStart[0][1] = ImageHeight - 1 - edge[5];
		FingerHoleEnd[0][0] = edge[6];
		FingerHoleEnd[0][1] = ImageHeight - 1 - edge[4];
	}

	if (HoleFlag == TRUE)
	{
		for (j = 0; j < 2; j++)
		{
			if (FingerHoleResult[j] == FALSE)
			{
				if (FingerHoleStart[j][1] != 0 && FingerHoleEnd[j][1] != 0)
				{
					if (HoleDetection(holeList, HoleNumber, FingerHoleStart, FingerHoleEnd, j, ThresholdFlag) == TRUE)
					{
						if (HoleNumber[j] < Hole_Length || holeList[j][0][0] != holeList[j][HoleNumber[j] - 1][0])
						{
							FingerHoleResult[j] = FALSE;
						}
						else
						{
							FingerHoleResult[j] = TRUE;
						}
					}
					else
					{
						HoleNumber[j] = 0;
					}
				}
			}
		}
	}

	for (i = 0; i < 2; i++)
	{
		for (j = 0; j < HoleNumber[i]; j++)
		{
			ThresholdFlag[holeList[i][j][0] + holeList[i][j][1] * ImageWidth] = 128;
		}
	}

	//手没张开，直接设为估计值
	bool index[2] = {false};
	if (FingerHoleResult[0] == FALSE || HoleNumber[0] < Hole_Length)
	{
		index[0] = true;
	}
	if (FingerHoleResult[1] == FALSE || HoleNumber[1] < Hole_Length)
	{

		index[1] = true;
	}
	for (int i = 0; i < 0; i++) //TODO: no little-rings finger
	{
		if (index[i])
		{
			holeList[i][0][0] = FingerHoleStart[i][0];
			holeList[i][0][1] = FingerHoleStart[i][1];

			holeList[i][1][0] = FingerHoleStart[i][0] + 2 * Hole_Width;
			holeList[i][1][1] = (FingerHoleStart[i][1] + FingerHoleEnd[i][1]) / 2;

			holeList[i][2][0] = FingerHoleEnd[i][0];
			holeList[i][2][1] = FingerHoleEnd[i][1];

			HoleNumber[i] = 3;
			index[i] = false;
		}
	}
	for (int i = 0; i < 2; i++)
	{
		if (index[i])
			return FALSE;
	}

	if (LnkeyPointDetection(holeList, HoleNumber, Sx, Sy) == FALSE)
	{
		return FALSE;
	}

	for (i = 0; i < 4; i++)
	{
		ThresholdFlag[Sy[i] + Sx[i] * ImageWidth] = BLACK;
	}

	ROIExtraction(Image, roiImg, Sx, Sy); //

	return TRUE;
}

int LnkeyPointDetection(int Boundary[2][BOUNDARYPOINTS][2], int HoleNumber[2], int Sx[4], int Sy[4])
{
	int i, j;
	int ptpair = 0;
	float m = 0, c = 0, cy = 0;
	int mp = 0;
	unsigned int maxValue = 0;
	unsigned int Xpart = 0, Ypart = 0;
	float r = 0;
	int SubListindex1[50];
	int SubListindex2[50];
	int Sindex1 = 0;
	int Sindex2 = 0;
	int Si1 = 0;
	int Si2 = 0;
	float Distance2;
	float distance;
	float x0, x2, y0, y2;
	float b, a, d, T;
	float x3, x4, y3, y4;
	int xa, ya, xb, yb, xc, yc, xd, yd;
	float xaf, yaf, xbf, ybf, xcf, ycf, xdf, ydf;
	float xcenter, ycenter;
	int k, L;
	int Flag2[2] = {TRUE, TRUE};
	int maxpointer1 = 0, maxstarty1 = 0, maxendy1 = 0, maxpvalue1 = 0;
	int maxpointer2 = 0, maxstarty2 = 0, maxendy2 = 0, maxpvalue2 = 0;
	float linetemppoint;
	float ROIDistFromKey2 = ROIDistFromKey;

	for (i = 0; i < HoleNumber[0]; i++)
	{
		if (Boundary[0][i][0] > maxpvalue1)
		{
			maxpvalue1 = Boundary[0][i][0];
			maxpointer1 = i;
		}
	}
	for (j = 0; j < HoleNumber[1]; j++)
	{
		if (Boundary[1][j][0] > maxpvalue2)
		{
			maxpvalue2 = Boundary[1][j][0];
			maxpointer2 = j;
		}
	}
	maxP1Index = maxpointer1;
	maxP2Index = maxpointer2;
	maxendy1 = 0;
	for (i = 0; i < maxpointer1; i++)
	{
		if (Boundary[0][i][0] >= maxpvalue1 - 10)
		{
			maxstarty1 = i;
			break;
		}
	}
	maxendy1 = HoleNumber[0];
	for (i = HoleNumber[0]; i > maxpointer1; i--)
	{
		if (Boundary[0][i][0] >= maxpvalue1 - 10)
		{
			maxendy1 = i;
			break;
		}
	}
	maxstarty2 = 0;
	for (j = 0; j < maxpointer2; j++)
	{
		if (Boundary[1][j][0] >= maxpvalue2 - 10)
		{
			maxstarty2 = j;
			break;
		}
	}
	maxendy2 = HoleNumber[1];
	for (j = HoleNumber[1]; j > maxpointer2; j--)
	{
		if (Boundary[1][j][0] >= maxpvalue2 - 10)
		{
			maxendy2 = j;
			break;
		}
	}
	startP1 = maxstarty1;
	endP1 = maxendy1;
	startP2 = maxstarty2;
	endP2 = maxendy2;
	for (i = maxstarty1; i < maxendy1; i++)
	{
		for (j = maxstarty2; j < maxendy2; j++)
		{
			if (Boundary[0][i][1] != Boundary[1][j][1])
			{
				m = (float)(Boundary[0][i][0] - Boundary[1][j][0]) / (float)(Boundary[0][i][1] - Boundary[1][j][1]);
				c = (float)(Boundary[0][i][0]) - m * (float)(Boundary[0][i][1]);
				Flag2[0] = TRUE;
				Flag2[1] = TRUE;

				for (k = 0; k < HoleNumber[0]; k++)
				{
					linetemppoint = (float)Boundary[0][k][0] - m * (float)Boundary[0][k][1] - c;

					if (linetemppoint > 0.5)
					{
						if (k != i)
						{
							Flag2[0] = FALSE;
							break;
						}
					}
				}
				if (Flag2[0] == TRUE)
				{
					for (L = 0; L < HoleNumber[1]; L++)
					{
						linetemppoint = (float)Boundary[1][L][0] - m * (float)Boundary[1][L][1] - c;

						if (linetemppoint > 0.5)
						{
							if (L != j)
							{
								Flag2[1] = FALSE;
								break;
							}
						}
					}
				}
			}
			else
			{
				Flag2[0] = TRUE;
				Flag2[1] = TRUE;
				for (k = 0; k < HoleNumber[0]; k++)
				{
					if (Boundary[0][k][1] > Boundary[0][i][1])
					{
						if (k != i)
						{
							Flag2[0] = FALSE;
							break;
						}
					}
				}
				if (Flag2[0] == TRUE)
				{
					for (L = 0; L < HoleNumber[1]; L++)
					{
						if (Boundary[1][L][1] > Boundary[0][j][1])
						{
							if (L != j)
							{
								Flag2[0] = FALSE;
								break;
							}
						}
					}
				}
			}
			if (Flag2[0] == TRUE && Flag2[1] == TRUE)
			{
				pairList[ptpair][0] = i;
				pairList[ptpair][1] = j;
				ptpair++;
			}
		}
	}
	pairListNum = ptpair;
	if (ptpair == 0)
	{
		return FALSE;
	}
	mp = 0;
	maxValue = 0;
	Xpart = 0;
	Ypart = 0;
	for (i = 0; i < ptpair; i++)
	{
		Xpart = Boundary[0][pairList[i][0]][1] - Boundary[1][pairList[i][1]][1];
		Xpart = Xpart * Xpart;
		Ypart = Boundary[0][pairList[i][0]][0] - Boundary[1][pairList[i][1]][0];
		Ypart = Ypart * Ypart;
		if (Xpart + Ypart > maxValue)
		{
			maxValue = Xpart + Ypart;
			mp = i;
		}
	}

	if (Boundary[0][pairList[mp][0]][1] != Boundary[1][pairList[mp][1]][1])
	{
		m = (float)(Boundary[0][pairList[mp][0]][0] - Boundary[1][pairList[mp][1]][0]) / (float)(Boundary[0][pairList[mp][0]][1] - Boundary[1][pairList[mp][1]][1]);
	}
	else
	{
		m = (float)(Boundary[0][pairList[mp][0]][0] - Boundary[1][pairList[mp][1]][0]) / (float)(0.01);
	}

	cy = 0;
	c = Boundary[0][pairList[mp][0]][0] - m * Boundary[0][pairList[mp][0]][1];
	Sindex1 = 0;
	Sindex2 = 0;
	r = 0;

	for (i = 0; i <= pairList[mp][0]; i++)
	{
		cy = (c - Boundary[0][i][0]);
		r = (m * Boundary[0][i][1] + cy) * (m * Boundary[0][i][1] + cy) / (1 + m * m);
		if (r < 1)
		{
			SubListindex1[Sindex1] = i;
			Sindex1++;
		}
	}
	for (i = pairList[mp][1]; i < HoleNumber[1]; i++)
	{
		cy = (c - Boundary[1][i][0]);

		r = (m * Boundary[1][i][1] + cy) * (m * Boundary[1][i][1] + cy) / (1 + m * m);
		if (r < 1)
		{
			SubListindex2[Sindex2] = i;
			Sindex2++;
		}
	}
	maxValue = 0;
	Si1 = pairList[mp][0];
	Si2 = pairList[mp][1];

	for (i = 0; i < Sindex1; i++)
	{
		for (j = 0; j < Sindex2; j++)
		{
			Xpart = (Boundary[0][SubListindex1[i]][0] - Boundary[1][SubListindex2[j]][0]);
			Xpart = Xpart * Xpart;
			Ypart = (Boundary[0][SubListindex1[i]][1] - Boundary[1][SubListindex2[j]][1]);
			Ypart = Ypart * Ypart;
			if (maxValue < Xpart + Ypart)
			{
				maxValue = Xpart + Ypart;
				Si1 = SubListindex1[i];
				Si2 = SubListindex2[j];
			}
		}
	}

	lastP1Index = Si1;
	lastP2Index = Si2;

	distance = (float)sqrt((float)maxValue) / 1.20;
	Distance2 = (float)distance * distance;
	ROIDistFromKey = distance * 32 / 167 * 1.3;
	x0 = Boundary[0][Si1][1];
	x2 = Boundary[1][Si2][1];
	y0 = Boundary[0][Si1][0];
	y2 = Boundary[1][Si2][0];

	if (y0 != y2)
	{
		m = -(x0 - x2) / (y0 - y2);
		c = y2 - m * x2;
		cy = (c - y2);
		a = (1 + m * m);
		b = (2 * m * cy - 2 * x2);
		d = x2 * x2 + cy * cy - ROIDistFromKey * ROIDistFromKey;
		T = (float)sqrt(b * b - 4 * a * d);
		x3 = ((-b + T) / (2 * a));
		x4 = ((-b - T) / (2 * a));
		y3 = (m * x3 + c);
		y4 = (m * x4 + c);
		if (y4 > y3)
		{
			xaf = x4;
			yaf = y4;
		}
		else
		{
			xaf = x3;
			yaf = y3;
		}
		d = x2 * x2 + cy * cy - (distance + ROIDistFromKey) * (distance + ROIDistFromKey);
		T = (float)sqrt(b * b - 4 * a * d);
		x3 = ((-b + T) / (2 * a));
		x4 = ((-b - T) / (2 * a));
		y3 = (m * x3 + c);
		y4 = (m * x4 + c);
		if (y4 > y3)
		{
			xbf = x4;
			ybf = y4;
		}
		else
		{
			xbf = x3;
			ybf = y3;
		}

		c = y0 - m * x0;
		cy = (c - y0);
		a = (1 + m * m);
		b = (2 * m * cy - 2 * x0);
		d = x0 * x0 + cy * cy - ROIDistFromKey * ROIDistFromKey;
		T = (float)sqrt(b * b - 4 * a * d);
		x3 = ((-b + T) / (2 * a));
		x4 = ((-b - T) / (2 * a));
		y3 = (m * x3 + c);
		y4 = (m * x4 + c);
		if (y4 > y3)
		{
			xdf = x4;
			ydf = y4;
		}
		else
		{
			xdf = x3;
			ydf = y3;
		}

		d = x0 * x0 + cy * cy - (distance + ROIDistFromKey) * (distance + ROIDistFromKey);
		T = (float)sqrt(b * b - 4 * a * d);
		x3 = ((-b + T) / (2 * a));
		x4 = ((-b - T) / (2 * a));
		y3 = (m * x3 + c);
		y4 = (m * x4 + c);
		if (y4 > y3)
		{
			xcf = x4;
			ycf = y4;
		}
		else
		{
			xcf = x3;
			ycf = y3;
		}
	}
	else
	{
		distance = (float)sqrt(Distance2);
		xaf = x2;
		xbf = x2;
		xcf = x0;
		xdf = x0;
		yaf = y2 + ROIDistFromKey;
		ybf = y2 + ROIDistFromKey + distance;
		ycf = y0 + ROIDistFromKey + distance;
		ydf = y0 + ROIDistFromKey;
	}
	xa = (int)(xaf + 0.5);
	xb = (int)(xbf + 0.5);
	xc = (int)(xcf + 0.5);
	xd = (int)(xdf + 0.5);
	ya = (int)(yaf + 0.5);
	yb = (int)(ybf + 0.5);
	yc = (int)(ycf + 0.5);
	yd = (int)(ydf + 0.5);

	if (xa != xd)
	{
		xcenter = (xaf + xdf) / 2;
		ycenter = (yaf + ydf) / 2;
		m = (yaf - ydf) / (xaf - xdf);
		c = ycenter - m * xcenter;
		cy = c - ycenter;
		a = (1 + m * m);
		b = 2 * m * cy - 2 * xcenter;
		d = xcenter * xcenter + cy * cy - Distance2 / 4;
		T = (float)sqrt(b * b - 4 * a * d);
		x3 = ((-b + T) / (2 * a));
		x4 = ((-b - T) / (2 * a));
		y3 = (m * x3 + c);
		y4 = (m * x4 + c);
		xd = (int)(x4 + 0.5);
		yd = (int)(y4 + 0.5);
		xa = (int)(x3 + 0.5);
		ya = (int)(y3 + 0.5);
		xcenter = (xbf + xcf) / 2;
		ycenter = (ybf + ycf) / 2;
		c = ycenter - m * xcenter;
		cy = (c - ycenter);
		a = (1 + m * m);
		b = (2 * m * cy - 2 * xcenter);
		d = xcenter * xcenter + cy * cy - Distance2 / 4;
		T = (float)sqrt(b * b - 4 * a * d);
		x3 = ((-b + T) / (2 * a));
		x4 = ((-b - T) / (2 * a));
		y3 = (m * x3 + c);
		y4 = (m * x4 + c);
		xc = (int)(x4 + 0.5);
		yc = (int)(y4 + 0.5);
		xb = (int)(x3 + 0.5);
		yb = (int)(y3 + 0.5);
	}
	else
	{
		xa = (int)xaf;
		xb = (int)xbf;
		xc = (int)xbf;
		xd = (int)xaf;
		ya = (int)(yaf + ydf) / 2 + (int)(distance / 2);
		yb = (int)(ybf + ycf) / 2 + (int)(distance / 2);
		yc = (int)(ybf + ycf) / 2 - (int)(distance / 2);
		yd = (int)(yaf + ydf) / 2 - (int)(distance / 2);
	}

	Sx[0] = xa;
	Sx[1] = xb;
	Sx[2] = xc;
	Sx[3] = xd;
	Sy[0] = ya;
	Sy[1] = yb;
	Sy[2] = yc;
	Sy[3] = yd;

	return TRUE;
}

void SetImageSize(int width, int height)
{
	ImageWidth = width;
	ImageHeight = height;
	return;
}
